﻿//1.最大子数组和
//https://leetcode.cn/problems/maximum-subarray/description/

//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//子数组是数组中的一个连续部分。
//示例 1：
//输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
//输出：6
//解释：连续子数组[4, -1, 2, 1] 的和最大，为 6 。
//示例 2：
//输入：nums = [1]
//输出：1
//示例 3：
//输入：nums = [5, 4, -1, 7, 8]
//输出：23
//提示：
//1 <= nums.length <= 105
//- 104 <= nums[i] <= 104

//解法：
//dp[i]表示：以i为结尾的最大子数组的和
//最大子数组的和分两种情况，一种是长度为1即nums[i] 
//另一种是dp[i - 1] + nums[i]
 class Solution {
 public:
     int maxSubArray(vector<int>& nums) 
     {
         int n = nums.size();
         //多开一个空间方便初始化
         vector<int> dp(n + 1);
         int ret = INT_MIN;
         for(int i = 1;i <= n;i++)
         {
             dp[i] = max(nums[i - 1],dp[i - 1] + nums[i - 1]);
             if(dp[i] > ret) ret = dp[i]; 
         }
         return ret;
     }
 };


//2.环形子数组的最大和
//https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
//给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 
//环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
//子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
//示例 1：
//输入：nums = [1, -2, 3, -2]
//输出：3
//解释：从子数组[3] 得到最大和 3
//示例 2：
//输入：nums = [5, -3, 5]
//输出：10
//解释：从子数组[5, 5] 得到最大和 5 + 5 = 10
//示例 3：
//输入：nums = [3, -2, 2, -3]
//输出：3
//解释：从子数组[3] 和[3, -2, 2] 都可以得到最大和 3
//
//提示：
//n == nums.length
//1 <= n <= 3 * 104
//- 3 * 104 <= nums[i] <= 3 * 104​​​​​​​

//解法：
//该题子数组最大和分两种情况
//一是最大子数组和在数组nums中间部分
//二是最大子数组和是数组nums开头前一部分加上数组结尾的一部分，如示例2，最大子数组和为数组开头的5和结尾的5
//用f[i]表示：以i为结尾的最大子数组的和  
//用g[i]表示：以i为结尾的最小子数组的和，用整个数组的和sum减去最小的子数组的和就是最大子数组的和用ret表示
//f[i] = max(nums[i],f[i - 1] + nums[i])
//g[i] = min(nums[i],g[i - 1] + nums[i])
//最后求两种情况下最大的子数组的和

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        int n = nums.size();
        //多开一个空间方便初始化
        vector<int> f(n + 1), g(n + 1);
        //fmax记录最大的子数组的和 gmin记录最小的子数组的和 sum记录争个数组的和
        int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, f[i - 1] + x);
            fmax = max(fmax, f[i]);
            g[i] = min(x, g[i - 1] + x);
            gmin = min(gmin, g[i]);
            sum += x;
        }
        //如果gmin == sum 说明整个数组的元素都是负数，返回fmax即可，否则返回两种情况下求得的最大子数组的和
        return gmin == sum ? fmax : max(fmax, sum - gmin);
    }
};
//3.乘机最大子数组
//https://leetcode.cn/problems/maximum-product-subarray/
//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//测试用例的答案是一个 32 - 位 整数。
//示例 1:
//输入: nums = [2, 3, -2, 4]
//输出 : 6
//解释 : 子数组[2, 3] 有最大乘积 6。
//示例 2 :
//输入 : nums = [-2, 0, -1]
//输出 : 0
//解释 : 结果不能为 2, 因为[-2, -1] 不是子数组。
//提示 :
//1 <= nums.length <= 2 * 104
//- 10 <= nums[i] <= 10
//nums 的任何子数组的乘积都 保证 是一个 32 - 位 整数

//解法：
//用f[i]表示：以位置i为结尾的所有子数组的乘积最大值  
//用g[i]表示：以位置i为结尾的所有子数组的乘积最小值  
//f[i]分三种情况：
//(1)当子数组长度为一时，f[i] = nums[i]
//(2)当子数组长度不为一时
//1.nums[i]为正数，f[i] = f[i - 1] * nums[i] 
//2.nums[i]为负数，f[i] = g[i - 1] * nums[i] 
//g[i]同样如此
//所以f[i] = max(nums[i],max(f[i - 1] * nums[i],g[i - 1] * nums[i]))
//g[i] = min(nums[i],min(f[i - 1] * nums[i],g[i - 1] * nums[i]))
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        //多开一个空间方便初始化和填表
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, max(f[i - 1] * x, g[i - 1] * x));
            ret = max(ret, f[i]);
            g[i] = min(x, min(g[i - 1] * x, f[i - 1] * x));
        }
        return  ret;
    }
};


//4.乘积为正数的最长子数组长度
//https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/
//给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
//一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
//请你返回乘积为正数的最长子数组长度。
//示例  1：
//输入：nums = [1, -2, -3, 4]
//输出：4
//解释：数组本身乘积就是正数，值为 24 。
//示例 2：
//输入：nums = [0, 1, -2, -3, -4]
//输出：3
//解释：最长乘积为正数的子数组为[1, -2, -3] ，乘积为 6 。
//注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
//示例 3：
//输入：nums = [-1, -2, -3, 0, 1]
//输出：2
//解释：乘积为正数的最长子数组是[-1, -2] 或者[-2, -3] 。
//提示：
//1 <= nums.length <= 10 ^ 5
//- 10 ^ 9 <= nums[i] <= 10 ^ 9


//解法：
//用f[i]表示：以位置i为结尾的所有子数组的乘积为正数的最长长度
//用g[i]表示：以位置i为结尾的所有子数组的乘积为负数的最长长度
//当f[i]表示乘积为正数的子数组长度为一时，
//(1)nums[i]为正数，f[i] = 1
//(2)nums[i]为负数，f[i] = 0
//当f[i]表示乘积为正数的子数组长度大于一时，
//(1)nums[i]为正数，f[i] = f[i - 1] + 1
//(2)nums[i]为负数，f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1
//g[i]同理
//g[i]表示乘积为负数的子数组长度为一时，
//(1)nums[i]为正数，g[i] = 0
//(2)nums[i]为负数，g[i] = 1
//当g[i]表示乘积为负数的子数组长度大于一时，
//(1)nums[i]为正数，g[i] = g[i - 1] == 0 ？ 0 ： g[i - 1] + 1
//(2)nums[i]为负数，g[i] = f[i - 1] + 1
//当nums[i]大于0时，
//f[i] = 1 与f[i] = f[i - 1] + 1合并成f[i] = f[i - 1] + 1
//g[i] = 0与g[i] = g[i - 1] == 0 ？0 ：g[i - 1] + 1合并成g[i] = g[i - 1] == 0 ？ 0 ：g[i - 1] + 1
//当nums[i]小于0时
//f[i] = 0与f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1合并成f[i] = g[i - 1] == 0 ？0 : g[i - 1] + 1
//g[i] = 1与g[i] = f[i - 1] + 1合并成g[i] = f[i - 1] + 1
class Solution {
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};


//5.等差数列划分
//https://leetcode.cn/problems/arithmetic-slices/description/
//如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
//例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和[3, -1, -5, -9] 都是等差数列。
//给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
//子数组 是数组中的一个连续序列。
//示例 1：
//输入：nums = [1, 2, 3, 4]
//输出：3
//解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和[1, 2, 3, 4] 自身。
//示例 2：
//输入：nums = [1]
//输出：0
//提示：
//1 <= nums.length <= 5000
//- 1000 <= nums[i] <= 1000


//解法：
//dp[i]表示：以位置i元素结尾的等差数列的个数
//如果nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]成立
//所有以 nums[i-1] 结尾的等差数列都可以延长到 nums[i]
//另外，nums[i-2], nums[i-1], nums[i] 本身也构成一个新的长度为3的等差数列
//dp[i] = dp[i-1] + 1

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        int sum = 0;
        for (int i = 2; i < n; i++)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }
        return sum;
    }
};



//6.最长湍流子数组
//https://leetcode.cn/problems/longest-turbulent-subarray/description/
//给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
//如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
//更正式地来说，当 arr 的子数组 A[i], A[i + 1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
//若 i <= k < j ：
//当 k 为奇数时， A[k] > A[k + 1]，且
//当 k 为偶数时，A[k] < A[k + 1]；
//或 若 i <= k < j ：
//当 k 为偶数时，A[k] > A[k + 1] ，且
//当 k 为奇数时， A[k] < A[k + 1]。
//示例 1：
//输入：arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
//输出：5
//解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
//示例 2：
//输入：arr = [4, 8, 12, 16]
//输出：2
//示例 3：
//输入：arr = [100]
//输出：1
//提示：
//1 <= arr.length <= 4 * 104
//0 <= arr[i] <= 109

//解法：
//f[i]表示：以i位置元素结尾的所有子数组中，呈“上升”状态的最长湍流子数组长度,“上升”即nums[i - 1] < nums[i]
//g[i]表示：以i位置元素结尾的所有子数组中，呈“下降”状态的最长湍流子数组长度,“下降”即nums[i - 1] > nums[i]
//f[i]有三种表示：
//(1)当nums[i - 1] > nums[i]时，i位置元素即nums[i]单独呈“上升”状态 即f[i] = 1
//(2)当nums[i - 1] = nums[i]时，i位置元素即nums[i]单独呈“上升”状态 即f[i] = 1
//(3)当nums[i - 1] < nums[i]时，元素nums[i - 1]和nums[i]呈“上升”状态，则要求在i - 1位置呈“下降”状态的最长湍流子数组长度，
//而在i - 1位置呈“下降”状态的最长湍流子数组长度即g[i - 1]
//所以f[i] = g[i - 1] + 1
//总结:
//当nums[i - 1] >= nums[i]时，f[i] = 1
//当nums[i - 1] < nums[i]时，f[i] = g[i - 1] + 1
//g[i]同理
//当nums[i - 1] >= nums[i]时，g[i] = 1
//当nums[i - 1] < nums[i]时，g[i] = f[i - 1] + 1
//
class Solution {
public:
    int maxTurbulenceSize(vector<int>& nums)
    {
        int n = nums.size();
        //将所有元素初始化成1，
        //则只用考虑nums[i - 1] < nums[i]时,f[i] = g[i - 1] + 1和nums[i - 1] > nums[i]时,g[i] = f[i - 1] + 1
        vector<int> f(n, 1), g(n, 1);
        int x = 1, y = 1;
        for (int i = 1; i < n; i++)
        {
            if (nums[i - 1] < nums[i])
                f[i] = g[i - 1] + 1;
            if (nums[i - 1] > nums[i])
                g[i] = f[i - 1] + 1;
            x = max(x, f[i]);
            y = max(y, g[i]);
        }
        return max(x, y);
    }
};

//7.单词拆分
//https://leetcode.cn/problems/word-break/description/
//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
//注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
//示例 1：
//输入 : s = "leetcode", wordDict = ["leet", "code"]
//输出 : true
//解释 : 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
//示例 2：
//输入 : s = "applepenapple", wordDict = ["apple", "pen"]
//输出 : true
//解释 : 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//注意，你可以重复使用字典中的单词。
//示例 3：
//输入 : s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出 : false
//提示：
//1 <= s.length <= 300
//1 <= wordDict.length <= 1000
//1 <= wordDict[i].length <= 20
//s 和 wordDict[i] 仅由小写英文字母组成
//wordDict 中的所有字符串 互不相同


//解法：
//dp[i]表示：字符串 s 的前 i 个字符能否被拆分成字典中的单词
//对于每个位置i，检查所有j < i，如果dp[j] 为真（前j个字符可以拆分成字典中的单词且子串s[j + 1:i]在字典中则dp[i]为真


class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        s = ' ' + s;
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        int maxWordLen = 0;
        for (const auto& word : wordDict)
        {
            maxWordLen = max(maxWordLen, (int)word.size());
        }
        for (int i = 1; i <= n; i++)
        {
            //优化：只检查可能的单词长度,j指向在区间[0，i]中最后一个单词开始的下标
            for (int j = i; j >= 1 && (i - j + 1) <= maxWordLen; j--)
            {
                if (dp[j - 1] && set.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    // 找到一个匹配即可
                    break;
                }
            }
        }
        return dp[n];
    }
};



//8. 环绕字符串中唯一的子字符串
//https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/
//定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
//"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
//给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
//示例 1：
//输入：s = "a"
//输出：1
//解释：字符串 s 的子字符串 "a" 在 base 中出现。
//示例 2：
//输入：s = "cac"
//输出：2
//解释：字符串 s 有两个子字符串("a", "c") 在 base 中出现。
//示例 3：
//输入：s = "zab"
//输出：6
//解释：字符串 s 有六个子字符串("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
//提示：
//1 <= s.length <= 105
//s 由小写英文字母组成

//解法：
//dp[i]表示的是以位置i结尾的所有子串有多少个字串在base中出现过

class Solution {
public:
    int findSubstringInWraproundString(string s)
    {
        int n = s.size();
        //s全是由小写字母组成，所以单个字母一定在base中出现过
        vector<int> dp(n,1);
        //计算以每个位置结尾的字串在base出现的次数
        for (int i = 1; i < n; i++)
        {
            if (s[i - 1] + 1 == s[i] || s[i - 1] == 'z' && s[i] == 'a')
                dp[i] += dp[i - 1];
        }
        int hash[26] = { 0 };
        int ret = 0;
        //对于每个字符，记录以该字符结尾的字串的最大个数
        for (int i = 0; i < n; i++)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        // 统计所有不同子串的数量
        for (int i = 0; i < 26; i++)
            ret += hash[i];
        return ret;
    }
};